#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_OP 100
#define ROOT 1
#define FATHER(i) ((i) / 2)
#define LEFT(i)   ((i) * 2)
#define RIGHT(i)  ((i) * 2 + 1)
#define cmp >
#define swap(a, b){printf("swap(%d, %d)\n", a, b);__typeof(a)__c = (a);(a) = (b);(b) = __c;}

typedef struct PriorityQueue{
    int *data, *__data;
    int size, n;
} PriorityQueue;

PriorityQueue *iniPQ(int size){
    PriorityQueue *p =(PriorityQueue *)malloc(sizeof(PriorityQueue));
    p->__data = (int *)malloc(sizeof(int) * size);
    p->data = p->__data - ROOT; 
    p->size = size;
    p->n = 0;
    return p;
}

void clearPQ(PriorityQueue *p){
    if(p == NULL) return;
    free(p->__data);
    free(p);
    return;
}

int empty(PriorityQueue *p){
    return p->n == 0;
}

int full(PriorityQueue *p){
    return p->size == p->n;
}

int top(PriorityQueue *p){
    return p->data[ROOT];
}

void up_update(int *data, int i){
    printf("\nup_update: %d\n", data[i]);
    while(i > ROOT && data[i] cmp data[FATHER(i)]){
        swap(data[i], data[FATHER(i)]);
        i = FATHER(i);
    }
    printf("\n");
    return;
}

void down_update(int *data, int i, int n){
    printf("\ndown_update: %d\n", data[i]);
    while(LEFT(i) <= n){
        int idx = i, l = LEFT(i), r = RIGHT(i);
        if(data[l] cmp data[idx]) idx = l;
        if(r <= n && data[r] cmp data[idx]) idx = r;
        if(idx == i) break;
        swap(data[i], data[idx]);
        i = idx;
    }
    printf("\n");
    return;
}

int push(PriorityQueue *p, int x){
    if(full(p)) return 0;
    p->n += 1;
    p->data[p->n] = x;
    // find a suitable location for x
    up_update(p->data, p->n);
    return 1;
}

int pop(PriorityQueue *p){
    if(empty(p)) return 0;
    p->data[ROOT] = p->data[p->n];
    p->n -= 1;
    down_update(p->data, ROOT, p->n);
    return 1;
}

void output(PriorityQueue *p){
    printf("PQ(%d): ", p->n);
    for(int i = 1; i <= p->n; i++){
        printf("%d ", p->data[i]);
    }
    printf("\n");
    return;
}

int main(){
    int op, x;
    PriorityQueue *p = iniPQ(MAX_OP);
    while(~scanf("%d", &op)){
        if(op == 1){
            scanf("%d", &x);
            printf("insert %d to priority queue:\n", x);
            push(p, x);
            output(p);
        }else if(op == 0){
            printf("pop: %d\n", top(p));
            pop(p);
            output(p);
        }else{
            break;
        }
    }
    clearPQ(p);

    return 0;
}